Definition

For i≥1i \geq 1, language LL is in 𝚺ip\mathbf{\Sigma}_i^p if there exists a polynomial time TM MM and polynomial qq such that

x∈L⟺∃u1∈{0,1}q(|x|)∀u2∈{0,1}q(|x|)...Qiui∈{0,1}q(|x|)M(x,u1,...,ui)=1x \in L \iff \exists u_{1} \in \{0,1\}^{q(|x|)} \forall u_2 \in \{0,1\}^{q(|x|)}... Q_i u_i \in \{0,1\}^{q(|x|)} M(x,u_1,...,u_i)=1

where QiQ_i denotes (quantifier) ∀\forall or ∃\exists depending on whether ii is even or odd, respectively.

Then the polynomial hierarchy is the set 𝐏𝐇=∪i𝚺ip\mathbf{PH} = \cup_i \mathbf{\Sigma}_i^p.

See also

References

  1. https://en.wikipedia.org/wiki/Polynomial_hierarchy
  2. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, pp. 95-104.
  3. https://www.cl.cam.ac.uk/teaching/0910/L15/handout5.pdf